//给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 
//
// 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列
//，而 "AEC" 不是） 
//
// 题目数据保证答案符合 32 位带符号整数范围。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "rabbbit", t = "rabbit"
//输出：3
//解释：
//如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
//rabbbit
//rabbbit
//rabbbit 
//
// 示例 2： 
//
// 
//输入：s = "babgbag", t = "bag"
//输出：5
//解释：
//如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length, t.length <= 1000 
// s 和 t 由英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 662 👎 0

package com.cute.leetcode.editor.cn;
public class DistinctSubsequences {
    public static void main(String[] args) {
        Solution solution = new DistinctSubsequences().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * dp保存的是t取到i-1和s取到j-1时t在s中出现的个数
         * 两个都不是空字符串
         * 手动写了几种dp实际情况"rabbbit, rabbit" "babgbag, bag" "aaaaa, aa"
         * 然后才推导出了dp的状态转移方程
         * 我这里是先遍历的t后遍历的s，遍历方式不同的话初始化也不同
         * 注意dp在空串时的初始化
         */
        public int numDistinct(String s, String t) {
            int[][] dp = new int[t.length()+1][s.length()+1];
            for (int i = 0; i <= s.length(); i++) dp[0][i] = 1;//初始化dp，即t为空串的时候，必须全部初始化为1才行
            for (int i = 1; i <= t.length(); i++) {
                for (int j = i; j <= s.length(); j++) {
                    //相等的时候可以从两个方向推过来，dp[i][j-1]是只不考虑当前的s时的情况，即s不选取当前字符时的匹配情况
                    if (t.charAt(i-1) == s.charAt(j-1)) dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
                    else dp[i][j] = dp[i][j-1];
                }
            }
            return dp[t.length()][s.length()];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}